/*
 * @lc app=leetcode.cn id=313 lang=typescript
 *
 * [313] 超级丑数
 */

// @lc code=start

function nthSuperUglyNumber(n: number, primes: number[]): number {
  const m = primes.length;
  // 超级丑数
  const dp = new Array(n + 1).fill(1);
  // p位置的当前丑数和质因数的积，得到下一个超级丑数
  const p = new Array(m).fill(1);

  for (let i = 2; i <= n; i++) {
    const next: number[] = new Array(m).fill(0);
    let min = Number.POSITIVE_INFINITY;
    for (let j = 0; j < m; j++) {
      next[j] = dp[p[j]] * primes[j];
      min = Math.min(min, next[j]);
    }
    dp[i] = min;
    // 更新p指针
    for (let j = 0; j < m; j++) {
      if (next[j] === min) p[j]++;
    }
  }
  return dp[n];
}
// @lc code=end
